#include <bits/stdc++.h>

using namespace std;

const int X = 500000 + 10, N = 500 + 10, M = 1000 + 10, INF = 0x3f3f3f3f;

int res;

struct DLX
{
    int n, m, sz;//n行m列，sz代表节点数
    //U[X], D[X], L[X], R[X],分别表示上、下、左、右数组指针，记录行、列元素
    //row[],col[]分别表示指向列标元素和行标元素
    int U[X], D[X], L[X], R[X], row[X], col[X];
    int H[N], S[M];//H[]表示头指针，S[i]表示第i列中的结点数
    int head, tot, ans[N];//tot代表答案所包含的行数，ans[]记录答案
    void init(int _n, int _m)
    {
        n = _n, m = _m;
        for(int i = 0; i <= m; i++)//枚举列
            L[i] = i-1, R[i] = i+1, U[i] = D[i] = i, S[i] = 0;
            //指向左       指向右   上下指针是自己    0个结点
        head = 0, tot = 0, sz = m;
        L[head] = m, R[m] = head;//边界情况
        for(int i = 1; i <= n; i++) H[i] = -1;//初始化头指针为-1
    }
    void link(int r, int c)//连接
    {
        ++S[col[++sz]=c];
        row[sz] = r;
        D[sz] = D[c], U[D[c]] = sz;
        U[sz] = c, D[c] = sz;
        if(H[r] < 0) H[r] = L[sz] = R[sz] = sz;
        else R[sz] = R[H[r]], L[R[H[r]]] = sz, L[sz] = H[r], R[H[r]] = sz;
    }
    void del(int c)//删除
    {
        L[R[c]] = L[c], R[L[c]] = R[c];
        for(int i = D[c]; i != c; i = D[i])
            for(int j = R[i]; j != i; j = R[j])
                D[U[j]] = D[j], U[D[j]] = U[j], --S[col[j]];
    }
    void recover(int c)//覆盖
    {
        for(int i = U[c]; i != c; i = U[i])
            for(int j = L[i]; j != i; j = L[j])
                D[U[j]] = U[D[j]] = j, ++S[col[j]];
        R[L[c]] = L[R[c]] = c;
    }
    void dance(int dep)
    {
        if(R[head] == head)
        {
            res = min(res, dep-1);
            return;
        }
        if(dep-1 >= res) return;
        int c = R[head];
        for(int i = R[head]; i != head; i = R[i])
            if(S[i] < S[c]) c = i;
        del(c);
        for(int i = D[c]; i != c; i = D[i])
        {
            ans[dep] = row[i];
            for(int j = R[i]; j != i; j = R[j]) del(col[j]);
            dance(dep + 1);
            for(int j = L[i]; j != i; j = L[j]) recover(col[j]);
        }
        recover(c);
    }
} dlx;
int main()
{
    int t, n, m, p;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d", &n, &m, &p);
        dlx.init(p, n * m);
        int x1, y1, x2, y2;
        for(int i = 1; i <= p; i++)
        {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            for(int j = x1+1; j <= x2; j++)
                for(int k = y1+1; k <= y2; k++)
                {
                    dlx.link(i, (j-1)*m + k);
                }
        }
        res = INF;
        dlx.dance(1);
        if(res == INF) res = -1;
        printf("%d\n", res);
    }
    return 0;
}
